package leetcode.递归回溯BFSDFS;

/**
 * 解数独
 */
public class Test37解数独 {

    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0)
            return;
        searchRes(board);
    }

    /**
     * 暴力搜索，往格子里面填一个数然后判断是否重复，重复了就推回复原，换一个数继续
     *
     * 一直递归下去
     * @param board
     * @return
     */
    private boolean searchRes(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 当前格子要是空的（内容为 . ）才可以填
                if (board[i][j] != '.') {
                    continue;
                }
                // 填的话，就把 1~9 全部试一遍
                for (char num = '1'; num <= '9'; num++) {
                    // 首先，要判断有没有冲突元素
                    if (!isValid(board, i, j, num)) {
                        continue;
                    }
                    board[i][j] = num;
                    // 填完 i、j 这个格子后继续填下一个格子
                    // 那也就是重复执行 searchRes 方法
                    if (searchRes(board)) {
                        return true;
                    } else {
                        board[i][j] = '.';//回退之前的状态,本轮搜索失败,回退的时候也是递归的
                    }
                }
                //  上面 1~9 均填充失败，则返回 false，进行回溯
                return false;
            }
        }
        // 如果遍历结束后，没有返回 false，答案就是 true 了
        return true;
    }

    private boolean isValid(char[][] board, int i, int j, char num) {
        // 列有相同的,说明尝试错误.
        for (int row = 0; row < 9; row++) {
            if (board[row][j] == num) {
                return false;
            }
        }

        // 行有相同的,说明尝试错误.
        for (int col = 0; col < 9; col++) {
            if (board[i][col] == num) {
                return false;
            }
        }

        // 9宫格中有相同的,说明尝试错误.
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) {
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) {
                if (board[row][col] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}
